In a transmission between a source and a receiver, some transmission errors may occur. Error correcting codes can be used to detect and correct some of these errors. Low-Density Parity-Check (LDPC) Codes are a class of error correcting code: they are block codes (or equivalently parity-check codes) and are defined by a parity-check matrix H. They were introduced in 1963 by R. G. Gallager (in Gallager's Thesis, “Low-Density Parity-Check Codes”, 1963, MIT) in the case of LDPC codes over the Galois Field GF(2) and generalized by Mackay in 1998 (in D. J. C Mackay, M. C. Davey, “Low Density Check Code over GF(q)”, Cavendis Laboratory, Cambridge, United Kingdom, 1998) over a Galois Field of higher cardinality, i.e. GF(rq) where r is a prime number.
LDPC codes can be used in a variety of transmission systems, e.g. satellite communications, wireless transmissions, fiber optics, and a variety of storage media e.g. hard disk drive, optical disk, magnetic band.
An LDPC code is defined by a parity-check matrix H of size M rows by N columns, M being the number of constraints and N being the number of variables. A non-zero entry of the matrix at position (m,n) indicates that the variable vn participates in the constraint cm.
An LDPC parity check matrix is sparse: there is a small number of non-zero entries in the matrix compared to its size. Let N(m)={vn:Hmn≢0} denotes the set of variables vn that participate in the constraint cm and N(m)/n denotes the same set with variable vn excluded. Similarly, M(n)={cm:Hmn≢0} denotes the set of constraints cm in which the variable vn participates and M(n)/m denotes the same set with the constraint cm excluded. The cardinality of a set A is denoted by |A|.
A regular (j,k) LDPC code is such that: |N(m)|=k, m={1, . . . , M} and |M(n)|=j, n={1, . . . , N}. When the cardinality of these two sets is not independent of m and n respectively, the LDPC code is irregular.
LDPC codes can also be defined using their Tanner graph representation. It is a bipartite graph with variable nodes on one side and constraint nodes on the other side. Each variable node corresponds, in the binary case, to a bit of the codeword, and each constraint node corresponds to a parity-check constraint of the code. Edges in the graph attach variable nodes to constraint nodes indicating that the variable participates to the connected constraint.
FIG. 1 depicts an example of a very small LDPC code over GF(2) and its associated Tanner graph, where N=6 and M=4. The variable nodes 10, 11, 12, 13, 14, 15 are connected to the constraint nodes 16, 17, 18, 19 through some edges. The variable to constraint messages Zmn(i) and the constraint to variable messages Lnm(i) are exchanged along these edges. The LDPC code illustrated in FIG. 1 corresponds to the following parity check matrix H with 6 columns representing variables v0 to v5 and 4 rows representing constraints c0 to c3:
  H  =            (                                    1                                1                                1                                0                                0                                0                                                1                                0                                0                                1                                1                                0                                                0                                1                                1                                0                                0                                1                                                0                                0                                0                                1                                1                                1                              )        .  
The graph shows 6 variables v0 to v5 (10 to 15) connected to constraints c0 to c3 (16 to 19) according to matrix H.
Thus, for example, variables v0, v1 and v2 are connected to the first constraint c0 according to the first row of H.
|N(m)| is called the weight or degree of the constraint cm. |M(n)| is called the weight or degree of the variable vn.